/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30/FONT#10=ZERO30
␈↓ ↓H␈↓␈↓ ε(draft␈↓ H


␈↓ ↓H␈↓α␈↓ αhMINIMAL INFERENCE - A WAY OF JUMPING TO CONCLUSIONS

␈↓ ↓H␈↓Abstract:␈αHumans␈αand␈αintelligent␈αcomputer␈αprograms␈αmust␈αoften␈αjump␈αto␈αthe␈αconclusion␈α
that␈αthe
␈↓ ↓H␈↓objects␈αthey␈αknow␈αabout␈αare␈αthe␈αonly␈αrelevant␈αobjects␈αinvolved␈αin␈αa␈αproblem.␈α
 ␈↓↓Minimal␈αinference␈↓
␈↓ ↓H␈↓is one formalization of this kind of approximate reasoning.
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 91


␈↓ ↓H␈↓αMinimal entailment

␈↓ ↓H␈↓␈↓ α_␈↓↓Minimal␈α⊂reasoning␈↓␈α⊂has␈α⊂a␈α⊂semantic␈α⊂form␈α⊂called␈α⊂␈↓↓minimal␈α⊂entailment␈↓␈α⊂and␈α⊂a␈α⊃syntactic␈α⊂form
␈↓ ↓H␈↓called ␈↓↓minimal inference␈↓.  We begin with ␈↓↓minimal entailment␈↓.

␈↓ ↓H␈↓␈↓ α_Let␈α
␈↓↓A␈↓␈α
be␈α
a␈α
set␈α
of␈α
sentences␈α
of␈α
first␈α
order␈α
logic␈α
and␈α
␈↓↓p␈↓␈α
a␈α
sentence.␈α
 As␈α
is␈α
customary␈α
in␈α
logic,␈α
we
␈↓ ↓H␈↓say␈α
that␈α
␈↓↓A␈α
entails␈αp␈↓␈α
(written␈α
␈↓↓A␈α
␈↓πq␈↓↓␈α
p␈↓)␈αiff␈α
␈↓↓p␈↓␈α
is␈α
true␈αin␈α
all␈α
models␈α
of␈α
␈↓↓A.␈↓␈α Suppose␈α
␈↓↓M1␈↓␈α
and␈α
␈↓↓M2␈↓␈αare␈α
two
␈↓ ↓H␈↓models␈αof␈α
a␈αset␈αof␈α
sentences␈αin␈αa␈α
multi-sorted␈αlogic.␈α
 We␈αcall␈α␈↓↓M1␈↓␈α
a␈αsubmodel␈αof␈α
␈↓↓M2␈↓␈α(written␈α␈↓↓M1␈α
≤
␈↓ ↓H␈↓↓M2␈↓)␈α⊗iff␈α⊗␈↓↓domain(M1)␈α⊗⊂␈α⊗domain(M2)␈↓,␈α⊗and␈α∃the␈α⊗predicates␈α⊗when␈α⊗applied␈α⊗to␈α⊗the␈α⊗elements␈α∃of
␈↓ ↓H␈↓␈↓↓domain(M1)␈↓␈αhave␈αthe␈αsame␈αvalues␈αin␈α␈↓↓M2␈↓␈αthat␈αthey␈αhave␈αin␈α␈↓↓M1.␈↓␈α ␈↓↓M␈↓␈αis␈αcalled␈αa␈αminimal␈αmodel␈αof
␈↓ ↓H␈↓␈↓↓A␈↓␈αiff␈αit␈αis␈αnot␈αa␈αproper␈αextension␈αof␈αanother␈αmodel.␈α We␈αsay␈αthat␈α␈↓↓A␈↓␈α␈↓↓minimally␈αentails␈αp␈↓␈α(written␈α␈↓↓A
␈↓ ↓H␈↓↓␈↓πq␈↓βm␈↓↓ p␈↓) iff ␈↓↓p␈↓ is true in all minimal models of ␈↓↓A.␈↓

␈↓ ↓H␈↓␈↓ α_We␈α⊂first␈α⊂show␈α⊂that␈α⊃minimal␈α⊂entailment␈α⊂is␈α⊂not␈α⊃equivalent␈α⊂to␈α⊂ordinary␈α⊂entailment␈α⊃in␈α⊂any
␈↓ ↓H␈↓logical␈αsystem␈αor␈αto␈αany␈αform␈αof␈αdeduction.␈α For␈αany␈αform␈αof␈αdeduction,␈αif␈α␈↓↓A␈α␈↓πr␈↓↓␈αp␈↓␈αand␈α␈↓↓A␈α⊂␈αB␈↓,␈αthen
␈↓ ↓H␈↓␈↓↓B␈α
␈↓πr␈↓↓␈α
p␈↓.␈α We␈α
may␈α
call␈α
this␈αproperty␈α
␈↓↓monotonicity␈↓.␈α
 Exactly␈αthe␈α
same␈α
proof␈α
that␈αproved␈α
␈↓↓p␈↓␈α
from␈α␈↓↓A␈↓␈α
will
␈↓ ↓H␈↓prove␈α
it␈α
from␈α
␈↓↓B.␈↓␈α
 Entailment␈αalso␈α
has␈α
this␈α
property;␈α
if␈α␈↓↓p␈↓␈α
is␈α
true␈α
in␈α
all␈α
models␈αof␈α
␈↓↓A,␈↓␈α
it␈α
is␈α
true␈αin␈α
all
␈↓ ↓H␈↓models␈αof␈α␈↓↓B,␈↓␈αbecause␈αthe␈αlatter␈αare␈αa␈αsubset␈αof␈αthe␈αmodels␈αof␈α␈↓↓A.␈↓␈αHowever,␈αminimal␈αentailment␈αis
␈↓ ↓H␈↓not␈αmonotonic.␈α
 Namely,␈αconsider␈α
the␈αnull␈α
set␈α␈↓↓N␈↓␈αof␈α
sentences.␈α Its␈α
minimal␈αmodel␈α
is␈αa␈αdomain␈α
with
␈↓ ↓H␈↓one␈α
element␈α
(in␈α
most␈αformalizations)␈α
so␈α
that␈α
the␈α
sentence␈α␈↓↓∀x y.x = y␈↓␈α
is␈α
minimally␈α
entailed␈α
by␈α␈↓↓N.␈↓
␈↓ ↓H␈↓However, the set ␈↓↓B␈↓ consisting of the negation of this sentence certainly contains the null set ␈↓↓N␈↓.

␈↓ ↓H␈↓␈↓ α_Here␈α
are␈α
some␈α
mathematical␈α
examples.␈α
 The␈α
minimal␈α
model␈α
of␈α
the␈α
Peano␈α∞axioms␈α
without
␈↓ ↓H␈↓the␈αschema␈αof␈α
induction␈αis␈αthe␈α
standard␈αmodel␈αof␈α
the␈αintegers␈αprovided␈α
the␈αconstant␈α0␈αis␈α
explicitly
␈↓ ↓H␈↓mentioned.␈α The␈αsystem␈αconsisting␈αonly␈αof␈αthe␈αaxioms␈αfor␈αthe␈α␈↓↓successor␈↓␈αoperation␈αomitting␈αaxioms
␈↓ ↓H␈↓for␈α0␈α
has␈αno␈αminimal␈α
model,␈αbecause␈αany␈α
model␈αhas␈αa␈α
submodel.␈α There␈αis␈α
also␈αno␈αminimal␈α
model
␈↓ ↓H␈↓if␈α
0␈αis␈α
characterized␈α
only␈αby␈α
an␈αexistential␈α
axiom,␈α
␈↓↓∃z.∀x.successor x ≠ z␈↓.␈α The␈α
minimal␈α
model␈αof
␈↓ ↓H␈↓the␈α
axioms␈α
for␈α
group␈α
theory␈α
is␈α
the␈α
group␈α
of␈α
one␈α
element.␈α
 If␈α
we␈α
add␈α
a␈α
sentence␈α
asserting␈αthat␈α
there
␈↓ ↓H␈↓is␈αmore␈αthan␈αone␈αelement,␈αthen␈αthe␈αminimal␈αmodels␈αare␈αthe␈αcyclic␈αgroups␈αof␈αprime␈αorder␈α
and␈αthe
␈↓ ↓H␈↓infinite cyclic group.



␈↓ ↓H␈↓αMinimal inference.

␈↓ ↓H␈↓␈↓ α_Minimal␈αentailment␈α
is␈αa␈αsemantic␈α
mode␈αof␈αreasoning.␈α
 As␈αMartin␈αDavis␈α
points␈αout,␈αit␈α
is␈αin
␈↓ ↓H␈↓general␈α∩infinitary.␈α⊃ Indeed,␈α∩since␈α⊃the␈α∩minimal␈α∩model␈α⊃of␈α∩the␈α⊃usual␈α∩first␈α⊃order␈α∩axioms␈α∩for␈α⊃the
␈↓ ↓H␈↓integers␈αis␈αthe␈α␈↓↓standard␈αmodel␈↓,␈αthe␈αminimal␈αconsequences␈αof␈αthe␈αaxioms␈αare␈αjust␈αthe␈αtrue␈αsentences
␈↓ ↓H␈↓of␈α→arithmetic,␈α_and␈α→this␈α_set␈α→isn't␈α_recursively␈α→enumerable␈α_or␈α→even␈α_arithmetic.␈α→ Here␈α→is␈α_a
␈↓ ↓H␈↓corresponding␈αsyntactic␈αmode␈α
of␈αreasoning.␈α Since␈α
by␈αG␈↓
:␈↓odel's␈αtheorem␈α
it␈αwon't␈αbe␈α
complete,␈αthere
␈↓ ↓H␈↓will be stronger modes.

␈↓ ↓H␈↓␈↓ α_The␈α
idea␈α
is␈α
to␈α
imitate␈α
the␈α
axiom␈α
schema␈αof␈α
induction.␈α
 Let␈α
␈↓↓A␈↓␈α
be␈α
the␈α
conjunction␈α
of␈αa␈α
certain
␈↓ ↓H␈↓subset␈α
of␈αour␈α
axioms␈α
called␈αthe␈α
primary␈α
axioms.␈α The␈α
criterion␈α
for␈αcalling␈α
some␈α
axioms␈αprimary
␈↓ ↓H␈↓and␈αothers␈αsecondary␈αis␈αnot␈αyet␈αentirely␈αclear,␈αbut␈αit␈αseems␈αclear␈αthat␈αsome␈αseparation␈αis␈αdesirable.
␈↓ ↓H␈↓Let␈α␈↓↓A␈↓	␈↓#
F␈↓#␈↓␈αbe␈αthe␈αresult␈αof␈αrelativizing␈α␈↓↓A␈↓␈αwith␈αrespect␈αto␈αthe␈αpredicate␈αparameter␈α␈↓	F␈↓.␈α (␈↓↓A␈↓	␈↓#
F␈↓#␈↓␈αis␈αobtained
␈↓ ↓H␈↓from␈α
␈↓↓A␈↓␈α
by␈α
replacing␈α
every␈α
universal␈αquantifier␈α
␈↓↓∀x␈↓␈α
by␈α
␈↓↓∀x.␈↓	F␈↓↓(x) ⊃␈↓␈α
and␈α
every␈α
existential␈αquantifier
␈↓ ↓H␈↓␈↓↓∃x␈↓␈α
by␈α
␈↓↓∃x.␈↓	F␈↓↓(x) ∧␈↓.␈α
 For␈αeach␈α
constant␈α
␈↓↓a␈↓␈α
appearing␈αin␈α
␈↓↓A,␈↓␈α
we␈α
must␈αadjoin␈α
␈↓	F␈↓↓(a)␈↓␈α
and␈α
for␈αeach␈α
function
␈↓ ↓H␈↓symbol ␈↓↓f,␈↓ we must adjoin the axiom ␈↓↓∀x.(␈↓	F␈↓↓(x) ⊃ ␈↓	F␈↓↓(f(x))␈↓)).  We introduce the schema
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 92


␈↓ ↓H␈↓␈↓ α_␈↓↓A␈↓	␈↓#
F␈↓#␈↓↓ ⊃ ∀x.␈↓	F␈↓↓(x)␈↓

␈↓ ↓H␈↓which␈α∞we␈α∞call␈α∂␈↓↓the␈α∞minimal␈α∞completion␈α∂schema␈↓␈α∞of␈α∞␈↓↓A␈↓␈α∂and␈α∞write␈α∞␈↓↓MCS(A)␈↓.␈α∂ We␈α∞will␈α∞call␈α∂the␈α∞system
␈↓ ↓H␈↓obtained␈α
by␈α
adjoining␈α the␈α
schema␈α
␈↓↓MCS(A)␈↓␈αto␈α
the␈α
axiom␈α␈↓↓A␈↓␈α
the␈α
␈↓↓minimal␈αcompletion␈α
of␈α
A␈↓,␈αwriting␈α
it
␈↓ ↓H␈↓␈↓↓MC(A)␈↓.␈α
 ␈↓↓MCS(A)␈↓␈α
is␈α∞an␈α
attempt␈α
to␈α∞assert␈α
that␈α
the␈α
only␈α∞objects␈α
are␈α
those␈α∞required␈α
to␈α
exist␈α∞by␈α
the
␈↓ ↓H␈↓axioms␈α␈↓↓A.␈α
 ␈↓␈α       Here␈αis␈α
a␈αtrivial␈α
example␈αof␈αa␈α
minimal␈αcompletion.␈α Suppose␈α
we␈αhave␈α
a␈αsingle
␈↓ ↓H␈↓axiom␈α␈↓↓ok(a)␈↓␈αin␈αour␈αprimary␈αset.␈α Its␈αrelativization␈αwill␈αbe␈α␈↓	F␈↓↓(a) ∧ ok(a)␈↓.␈α The␈αminimization␈αschema
␈↓ ↓H␈↓is then

␈↓ ↓H␈↓␈↓ α_␈↓	F␈↓↓(a) ∧ ok(a) ⊃ ∀x.␈↓	F␈↓↓(x)␈↓.

␈↓ ↓H␈↓If␈α
we␈αsubstitute␈α
␈↓↓λx.(x = a)␈↓␈αfor␈α
␈↓	F␈↓␈α
in␈αthe␈α
schema␈αwe␈α
can␈α
conclude␈α␈↓↓∀x.(x = a)␈↓␈α
which␈αcharacterizes␈α
the
␈↓ ↓H␈↓minimal␈αmodel␈α
of␈αthat␈αaxiom.␈α
 Indeed,␈αMartin␈αDavis␈α
showed␈αme␈αthat␈α
if␈αevery␈αmodel␈α
of␈α␈↓↓A␈↓␈α
has␈αa
␈↓ ↓H␈↓minimal␈αsubmodel␈αand␈αa␈αsentence␈α␈↓	f␈↓␈αis␈αtrue␈αin␈αany␈αsupermodel␈αof␈αany␈αmodel␈αof␈α␈↓	f␈↓,␈αthen␈α␈↓	f␈↓␈αis␈αtrue
␈↓ ↓H␈↓in all minimal models of ␈↓↓A␈↓ iff it is provable in the minimal completion of ␈↓↓A.␈↓

␈↓ ↓H␈↓␈↓ α_Let␈α␈↓↓s1␈↓␈α
be␈αthe␈αsentence␈α
␈↓↓∀x.ok(x) = p␈↓.␈α ␈↓↓p␈↓␈α
is␈αprovable␈αin␈α
␈↓↓MC({ok(a)} ∪ s1␈↓,␈αbut␈α
it␈αis␈αnot␈α
provable
␈↓ ↓H␈↓in␈α
␈↓↓MC({ok(a) ∧ s1}␈↓,␈α
because␈α
the␈αlater␈α
admits␈α
minimal␈α
models␈αin␈α
which␈α
␈↓↓p␈↓␈α
is␈αfalse␈α
and␈α
there␈α
is␈αan
␈↓ ↓H␈↓individual␈α␈↓↓b␈↓␈αsuch␈αthat␈α␈↓↓¬ok(b).␈↓␈α Therefore,␈αit␈αseems␈αthat␈αwe␈αhave␈αto␈αdivide␈αour␈αsentences␈αinto␈αtwo
␈↓ ↓H␈↓groups␈α
if␈α
we␈α
want␈α
minimal␈αinference␈α
to␈α
be␈α
useful␈α
-␈αa␈α
primary␈α
group␈α
whose␈α
minimal␈αcompletion
␈↓ ↓H␈↓we␈α∂form,␈α⊂and␈α∂a␈α⊂secondary␈α∂group␈α⊂which␈α∂is␈α∂used␈α⊂but␈α∂which␈α⊂is␈α∂not␈α⊂completed.␈α∂ The␈α⊂criteria␈α∂for
␈↓ ↓H␈↓deciding␈α∞in␈α
which␈α∞group␈α
to␈α∞put␈α
a␈α∞fact␈α
are␈α∞determined␈α
by␈α∞how␈α
we␈α∞want␈α
Occam's␈α∞razor␈α∞to␈α
work.
␈↓ ↓H␈↓We hope to clarify this in a later version of this paper.

␈↓ ↓H␈↓␈↓ α_We␈αcan␈α
form␈αthe␈αminimal␈α
completion␈αof␈αthe␈α
algebraic␈αPeano␈αaxioms␈α
as␈αfollows:␈α
 We␈αwrite
␈↓ ↓H␈↓the axioms

␈↓ ↓H␈↓1)␈↓ α8  ␈↓↓∀n.n' ≠ 0␈↓,

␈↓ ↓H␈↓2)␈↓ α8  ␈↓↓∀n.(n')␈↓∧-␈↓↓ = n␈↓,

␈↓ ↓H␈↓and

␈↓ ↓H␈↓3)␈↓ α8  ␈↓↓∀n.(n ≠ 0 ⊃ n␈↓∧-␈↓↓' = n)␈↓,

␈↓ ↓H␈↓where␈α⊂␈↓↓n'␈↓␈α⊂denotes␈α⊂the␈α⊂successor␈α⊂of␈α⊂␈↓↓n␈↓␈α⊂and␈α⊂␈↓↓n␈↓∧-␈↓␈α⊂denotes␈α⊂the␈α⊂predecessor␈α⊂of␈α⊂␈↓↓n␈↓.␈α⊃ The␈α⊂minimization
␈↓ ↓H␈↓schema of this set of axioms is

␈↓ ↓H␈↓4)␈↓ α8␈α ␈↓↓␈↓	F␈↓↓(0)␈α
∧␈α∀n.(␈↓	F␈↓↓(n)␈α⊃␈α
␈↓	F␈↓↓(n'))␈α∧␈α
∀n.(␈↓	F␈↓↓(n)␈α⊃␈α␈↓	F␈↓↓(n␈↓∧-␈↓↓))␈α
∧␈α∀n.(␈↓	F␈↓↓(n)␈α
⊃␈αn'␈α≠␈α
0)␈α∧␈α
∀n.(␈↓	F␈↓↓(n)␈α⊃␈α(n')␈↓∧-␈↓↓␈α
=
␈↓ ↓H␈↓↓n) ∧ ∀n.(␈↓	F␈↓↓(n) ⊃ (n≠0 ⊃ (n␈↓∧-␈↓↓)' = n))) ⊃ ∀n.␈↓	F␈↓↓(n)␈↓.

␈↓ ↓H␈↓␈↓ α_This␈αis␈αmuch␈αlonger␈α
than␈αthe␈αusual␈αschema␈α
of␈αinduction,␈αbut␈αcan␈α
be␈αshown␈αequivalent␈αto␈α
it.
␈↓ ↓H␈↓Notice␈αthat␈αthe␈αconjuncts␈αin␈αthe␈αpremiss␈αthat␈αrelativize␈αthe␈αaxioms␈α(1)-(3)␈αare␈αredundant;␈αbecause
␈↓ ↓H␈↓since␈α∂they␈α∂contain␈α⊂only␈α∂universal␈α∂quantifiers,␈α⊂they␈α∂are␈α∂weaker␈α⊂than␈α∂the␈α∂axioms␈α⊂they␈α∂relativize.
␈↓ ↓H␈↓Thus␈αPeano␈αarithmetic␈αis␈αthe␈αminimal␈αcompletion␈αof␈αits␈αalgebraic␈αsubsystem.␈α As␈αusual,␈αwhen␈αthe
␈↓ ↓H␈↓axioms␈αadmit␈α
only␈αinfinite␈α
models,␈αthe␈α
schema␈αwill␈α
not␈αbe␈α
sufficient␈αto␈α
enforce␈αthe␈αminimal␈α
model,
␈↓ ↓H␈↓and␈αthere␈αwill␈αalso␈αbe␈α␈↓↓non-standard␈↓␈αmodels.␈α Martin␈αDavis␈αhas␈αalso␈αshown␈αthat␈αif␈α0␈αis␈α
introduced
␈↓ ↓H␈↓through␈α∞an␈α∞existential␈α∞axiom␈α∞rather␈α∞than␈α∂as␈α∞a␈α∞constant,␈α∞the␈α∞minimal␈α∞completion␈α∂is␈α∞inconsistent;
␈↓ ↓H␈↓this corresponds to the fact that this system has no minimal model.
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 93


␈↓ ↓H␈↓αApplications

␈↓ ↓H␈↓␈↓ α_We␈α⊂envisage␈α⊂using␈α⊂minimal␈α⊂inference␈α⊂in␈α⊂AI␈α∂as␈α⊂follows:␈α⊂Suppose␈α⊂a␈α⊂system␈α⊂has␈α⊂a␈α∂certain
␈↓ ↓H␈↓collection␈α∞of␈α∞facts.␈α∞ It␈α∞may␈α∞or␈α∂may␈α∞not␈α∞have␈α∞all␈α∞the␈α∞relevant␈α∂facts,␈α∞but␈α∞it␈α∞is␈α∞reasonable␈α∞for␈α∂it␈α∞to
␈↓ ↓H␈↓conjecture␈α∞that␈α∞does␈α∞and␈α
examine␈α∞the␈α∞consequences␈α∞of␈α
the␈α∞conjecture.␈α∞ The␈α∞minimal␈α
completion
␈↓ ↓H␈↓axiom␈α
for␈αa␈α
set␈α
of␈αstatements␈α
is␈α
an␈αexpression␈α
of␈α
the␈αhypothesis␈α
that␈α
the␈αonly␈α
objects␈α
that␈αexist␈α
are
␈↓ ↓H␈↓those␈α⊃which␈α⊂must␈α⊃exist␈α⊂on␈α⊃the␈α⊂basis␈α⊃of␈α⊃these␈α⊂statements.␈α⊃ In␈α⊂order␈α⊃to␈α⊂make␈α⊃this␈α⊃workable␈α⊂in
␈↓ ↓H␈↓practice,␈αit␈αwill␈αbe␈αnecessary␈αto␈αapply␈αminimal␈αcompletion␈αto␈αsubsets␈αof␈αthe␈αfacts;␈αdifferent␈αsubsets
␈↓ ↓H␈↓will␈αgive␈α
rise␈αto␈α
different␈αconjectures.␈α Moreover,␈α
we␈αwill␈α
need␈αto␈αapply␈α
the␈αrelativization␈α
to␈αonly
␈↓ ↓H␈↓some␈α
of␈α∞the␈α
sorts␈α
of␈α∞individuals,␈α
so␈α
that␈α∞we␈α
can␈α
remain␈α∞non-committal␈α
about␈α
whether␈α∞there␈α
are
␈↓ ↓H␈↓more of certain sorts than our axioms prove to exist.

␈↓ ↓H␈↓␈↓ α_An␈α∩example␈α∩that␈α∩has␈α∩been␈α∩much␈α∩studied␈α⊃in␈α∩AI␈α∩and␈α∩which␈α∩contains␈α∩enough␈α∩detail␈α⊃to
␈↓ ↓H␈↓illustrate various issues is the ␈↓↓missionaries and cannibals␈↓ problem, stated as follows:

␈↓ ↓H␈↓␈↓ α_␈↓↓"Three␈α∪missionaries␈α∀and␈α∪three␈α∀cannibals␈α∪come␈α∀to␈α∪a␈α∪river.␈α∀ A␈α∪rowboat␈α∀that␈α∪seats␈α∀two␈α∪is
␈↓ ↓H␈↓↓available.␈α
 However,␈αif␈α
the␈αcannibals␈α
ever␈αoutnumber␈α
the␈αmissionaries␈α
on␈αeither␈α
bank␈αof␈α
the␈αriver,
␈↓ ↓H␈↓↓the outnumbered missionaries will be eaten.  How shall they cross the river?"␈↓.

␈↓ ↓H␈↓␈↓ α_Amarel␈α⊃(1971)␈α⊃considered␈α⊃various␈α⊃representations␈α⊃of␈α⊃the␈α⊃problem␈α⊃and␈α∩discussed␈α⊃criteria
␈↓ ↓H␈↓whereby␈α⊂the␈α⊃following␈α⊂representation␈α⊂is␈α⊃preferred␈α⊂for␈α⊂purposes␈α⊃of␈α⊂AI,␈α⊂because␈α⊃it␈α⊂leads␈α⊃to␈α⊂the
␈↓ ↓H␈↓smallest␈αstate␈αspace␈αthat␈αmust␈αbe␈αexplored␈αto␈αfind␈αthe␈αsolution.␈α We␈αrepresent␈αa␈αstate␈αby␈αthe␈α
triplet
␈↓ ↓H␈↓consisting␈α∞of␈α∞the␈α
numbers␈α∞of␈α∞missionaries,␈α
cannibals␈α∞and␈α∞boats␈α
on␈α∞the␈α∞initial␈α
bank␈α∞of␈α∞the␈α
river.
␈↓ ↓H␈↓The␈αinitial␈αconfiguration␈α
is␈α331,␈αthe␈αdesired␈α
final␈αconfiguration␈αis␈α000,␈α
and␈αone␈αsolution␈α
is␈αgiven
␈↓ ↓H␈↓by the sequence (331,220,321,300,311,110,221,020,031,010,021,000) of states.

␈↓ ↓H␈↓␈↓ α_We␈α⊂are␈α⊂not␈α⊂presently␈α⊂concerned␈α⊂with␈α⊂the␈α⊂heuristics␈α⊂of␈α⊂the␈α⊂problem␈α⊂but␈α⊂rather␈α⊂with␈α⊂the
␈↓ ↓H␈↓correctness␈αof␈αthe␈αreasoning␈αthat␈α
goes␈αfrom␈αthe␈αEnglish␈αstatement␈α
of␈αthe␈αproblem␈αto␈αAmarel's␈α
state
␈↓ ↓H␈↓space␈αrepresentation.␈α
 In␈αthe␈α
long␈αrun␈α
we␈αwould␈αlike␈α
a␈αcomputer␈α
to␈αcarry␈α
out␈αthis␈α
reasoning.␈α Of
␈↓ ↓H␈↓course␈αthere␈α
are␈αthe␈αwell␈α
known␈αdifficulties␈α
in␈αmaking␈αcomputers␈α
understand␈αEnglish,␈αbut␈α
suppose
␈↓ ↓H␈↓the␈α
English␈α
sentences␈α
describing␈α
the␈α
problem␈α
have␈α
already␈α
been␈α
rather␈α
directly␈α
translated␈α
into␈α
first
␈↓ ↓H␈↓order␈αlogic.␈α The␈αcorrectness␈αof␈αAmarel's␈αrepresentation␈αis␈αnot␈αan␈αordinary␈αlogical␈αconsequence␈αof
␈↓ ↓H␈↓these sentences for two reasons.

␈↓ ↓H␈↓␈↓ α_First,␈α∞nothing␈α∞has␈α∞been␈α∞stated␈α∞about␈α∞the␈α∞properties␈α∞of␈α∞boats␈α∞or␈α∞even␈α∞the␈α∞fact␈α∞that␈α
rowing
␈↓ ↓H␈↓across␈α∞the␈α∞river␈α
doesn't␈α∞change␈α∞the␈α∞numbers␈α
of␈α∞missionaries␈α∞or␈α∞cannibals␈α
or␈α∞the␈α∞capacity␈α∞of␈α
the
␈↓ ↓H␈↓boat.␈α These␈αare␈αa␈αconsequence␈αof␈αcommon␈αsense␈αknowledge,␈αso␈αlet␈αus␈αimagine␈αthat␈αcommon␈αsense
␈↓ ↓H␈↓knowledge, or at least the relevant part of it, is also expressed in first order logic.

␈↓ ↓H␈↓␈↓ α_The␈α∩second␈α⊃reason␈α∩we␈α⊃can't␈α∩␈↓↓deduce␈↓␈α∩the␈α⊃propriety␈α∩of␈α⊃Amarel's␈α∩representation␈α∩is␈α⊃deeper.
␈↓ ↓H␈↓Imagine␈α
giving␈α
someone␈α
the␈α
problem,␈α
and␈α
after␈αhe␈α
puzzles␈α
for␈α
a␈α
while,␈α
he␈α
suggests␈αgoing␈α
upstream
␈↓ ↓H␈↓half␈α
a␈α
mile␈α
and␈α
crossing␈α
on␈α
a␈α
bridge.␈α∞ "What␈α
bridge",␈α
you␈α
say.␈α
 "No␈α
bridge␈α
is␈α
mentioned␈α∞in␈α
the
␈↓ ↓H␈↓statement␈αof␈αthe␈αproblem."␈α And␈αthis␈αdunce␈αreplies,␈α"Well,␈αit␈αisn't␈αstated␈αthat␈αthere␈αisn't␈αa␈αbridge".
␈↓ ↓H␈↓You␈αlook␈αat␈αthe␈αEnglish␈αand␈αeven␈αat␈αthe␈αtranslation␈αof␈αthe␈αEnglish␈αinto␈αfirst␈αorder␈αlogic,␈αand␈αyou
␈↓ ↓H␈↓must␈α∂admit␈α∞that␈α∂it␈α∞isn't␈α∂stated␈α∂that␈α∞there␈α∂is␈α∞no␈α∂bridge.␈α∂ So␈α∞you␈α∂modify␈α∞the␈α∂problem␈α∂to␈α∞exclude
␈↓ ↓H␈↓bridges␈α∞and␈α∞pose␈α∂it␈α∞again,␈α∞and␈α∂the␈α∞dunce␈α∞proposes␈α∂a␈α∞helicopter,␈α∞and␈α∂after␈α∞you␈α∞exclude␈α∂that␈α∞he
␈↓ ↓H␈↓proposes␈αa␈α
winged␈αhorse␈αor␈α
that␈αthe␈α
others␈αhang␈αonto␈α
the␈αoutside␈α
of␈αthe␈αboat␈α
while␈αtwo␈αrow.␈α
 You
␈↓ ↓H␈↓now␈α
see␈α
that␈α
while␈α
a␈α
dunce,␈α
he␈α
is␈α
an␈αinventive␈α
dunce,␈α
and␈α
you␈α
despair␈α
of␈α
getting␈α
him␈α
to␈αaccept␈α
the
␈↓ ↓H␈↓problem␈αin␈α
the␈αproper␈α
puzzler's␈αspirit␈α
and␈αtell␈α
him␈αthe␈α
solution.␈α You␈α
are␈αfurther␈α
annoyed␈αwhen
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 94


␈↓ ↓H␈↓he␈αattacks␈αyour␈αsolution␈αon␈αthe␈αgrounds␈αthat␈αthe␈αboat␈αmight␈αnot␈αhave␈αoars.␈α After␈αyou␈αrectify␈α
that
␈↓ ↓H␈↓omission,␈α
he␈αsuggests␈α
that␈α
a␈αsea␈α
monster␈α
may␈αswim␈α
up␈α
the␈αriver␈α
and␈α
may␈αswallow␈α
the␈αboat.␈α
 Again
␈↓ ↓H␈↓you are frustrated, and you look for a mode of reasoning that will settle his hash once and for all.

␈↓ ↓H␈↓␈↓ α_Minimal␈αmodels␈α
and␈αminimal␈αinference␈α
may␈αgive␈αthe␈α
solution.␈α In␈αa␈α
minimal␈αmodel␈α
of␈αthe
␈↓ ↓H␈↓first␈α∞order␈α
logic␈α∞statement␈α
of␈α∞the␈α
problem,␈α∞there␈α∞is␈α
no␈α∞bridge␈α
or␈α∞helicopter.␈α
 "Ah",␈α∞you␈α∞say,␈α
"but
␈↓ ↓H␈↓there␈αaren't␈α
any␈αoars␈αeither".␈α
 No,␈αwe␈αget␈α
out␈αof␈α
that␈αas␈αfollows:␈α
 It␈αis␈αa␈α
part␈αof␈αcommon␈α
knowledge
␈↓ ↓H␈↓that␈αa␈αboat␈αcan␈αbe␈αused␈αto␈αcross␈αa␈αriver␈α␈↓↓unless␈αthere␈αis␈αsomething␈αwrong␈αwith␈αit␈αor␈α
something␈αelse
␈↓ ↓H␈↓↓prevents␈αusing␈αit␈↓,␈αand␈αin␈αthe␈αminimal␈αmodel␈αof␈αthe␈αfacts␈αthere␈αdoesn't␈αexist␈αsomething␈αwrong␈α
with
␈↓ ↓H␈↓the boat, and there isn't anything else to prevent its use.

␈↓ ↓H␈↓␈↓ α_The␈α∪non-monotonic␈α∩character␈α∪of␈α∩minimal␈α∪reasoning␈α∪is␈α∩just␈α∪what␈α∩we␈α∪want␈α∪here.␈α∩ The
␈↓ ↓H␈↓statement,␈α␈↓↓"There␈αis␈αa␈αbridge␈α
a␈αmile␈αupstream."␈↓␈αdoesn't␈αcontradict␈α
the␈αtext␈αof␈αthe␈αproblem,␈α
but␈αits
␈↓ ↓H␈↓addition invalidates the Amarel representation.

␈↓ ↓H␈↓␈↓ α_In␈α∞the␈α∞usual␈α∞sort␈α∞of␈α∞puzzle,␈α∞there␈α∞can␈α∞be␈α∞no␈α∞additional␈α∞source␈α∞of␈α∞information␈α∞beyond␈α∞the
␈↓ ↓H␈↓puzzle␈αand␈αcommon␈αsense␈α
knowledge.␈α Therefore,␈αthe␈αconvention␈α
can␈αbe␈αexplicated␈αas␈α
taking␈αthe
␈↓ ↓H␈↓minimal␈α∞completion␈α∞of␈α∞the␈α
puzzle␈α∞statement␈α∞and␈α∞a␈α∞certain␈α
part␈α∞of␈α∞common␈α∞sense␈α∞knowledge.␈α
 If
␈↓ ↓H␈↓one␈α
really␈α
were␈αsitting␈α
by␈α
a␈α
river␈αbank␈α
and␈α
these␈αsix␈α
people␈α
came␈α
by␈αand␈α
posed␈α
their␈αproblem,␈α
one
␈↓ ↓H␈↓wouldn't immediately take the minimal completion, but one would consider it as a hypothesis.

␈↓ ↓H␈↓␈↓ α_At␈αfirst␈αI␈αconsidered␈αthis␈αsolution␈αtoo␈αad␈αhoc␈αto␈αbe␈αacceptable,␈αbut␈αI␈αam␈αnow␈αconvinced␈αthat
␈↓ ↓H␈↓it␈αis␈αa␈αcorrect␈αexplication␈αof␈αthe␈α␈↓↓normal␈↓␈αsituation,␈αe.g.␈αunless␈αsomething␈αabnormal␈αexists,␈αan␈αobject
␈↓ ↓H␈↓can be used to carry out its normal function.

␈↓ ↓H␈↓␈↓ α_Some␈α∂have␈α∂suggested␈α∂that␈α∂the␈α∂difficulties␈α∂might␈α∂be␈α∂avoided␈α∂by␈α∂introducing␈α∂probabilities.
␈↓ ↓H␈↓They␈α∞suggest␈α∞that␈α∞the␈α∂existence␈α∞of␈α∞a␈α∞bridge␈α∞is␈α∂improbable.␈α∞ Well␈α∞the␈α∞whole␈α∂situation␈α∞involving
␈↓ ↓H␈↓cannibals␈α∂with␈α⊂the␈α∂postulated␈α⊂properties␈α∂is␈α⊂so␈α∂improbable␈α⊂that␈α∂it␈α⊂is␈α∂hard␈α⊂to␈α∂take␈α⊂seriously␈α∂the
␈↓ ↓H␈↓conditional␈α⊃probability␈α⊃of␈α∩a␈α⊃bridge␈α⊃given␈α⊃the␈α∩hypotheses.␈α⊃ Moreover,␈α⊃we␈α⊃mentally␈α∩propose␈α⊃to
␈↓ ↓H␈↓ourselves␈α→the␈α→normal␈α→non-bridge␈α→non-sea␈α→monster␈α→interpretation␈α→␈↓↓before␈↓␈α→considering␈α_these
␈↓ ↓H␈↓extraneous␈α
possibilities,␈α
let␈α
alone␈α
their␈α
probabilities,␈α
i.e.␈α
we␈α
usually␈α
don't␈α
even␈α
introduce␈α
the␈α
sample
␈↓ ↓H␈↓space␈αin␈αwhich␈αthese␈αpossibilities␈αare␈αassigned␈αwhatever␈αprobabilities␈αone␈αmight␈αconsider␈αthem␈αto
␈↓ ↓H␈↓have.␈α Therefore,␈αregardless␈αof␈αour␈αknowledge␈αof␈αprobabilities,␈αwe␈αneed␈αa␈αway␈αof␈αformulating␈αthe
␈↓ ↓H␈↓normal␈α
situation␈α
from␈α
the␈α
statement␈α
of␈α
the␈α
facts,␈α
and␈α
the␈α
minimal␈α
completion␈α
axioms␈α
seems␈α
to␈α
be␈α
a
␈↓ ↓H␈↓method.

␈↓ ↓H␈↓␈↓ α_Of␈αcourse,␈αwe␈αhaven't␈αgiven␈αan␈αexpression␈αof␈αcommon␈αsense␈αknowledge␈αin␈αa␈αform␈αthat␈αsays
␈↓ ↓H␈↓a␈α∂boat␈α∂can␈α⊂be␈α∂used␈α∂to␈α⊂cross␈α∂rivers␈α∂unless␈α∂there␈α⊂is␈α∂something␈α∂wrong␈α⊂with␈α∂it.␈α∂ In␈α⊂particular,␈α∂we
␈↓ ↓H␈↓haven't␈α⊂introduced␈α⊂into␈α∂our␈α⊂␈↓↓ontology␈↓␈α⊂(the␈α∂things␈α⊂that␈α⊂exist)␈α∂a␈α⊂category␈α⊂that␈α⊂includes␈α∂␈↓↓something
␈↓ ↓H␈↓↓wrong␈αwith␈αa␈αboat␈↓␈α
or␈αa␈αcategory␈αthat␈α
includes␈α␈↓↓something␈αthat␈αmay␈α
prevent␈αits␈αuse␈↓.␈α I␈α
imagine␈αthat
␈↓ ↓H␈↓many␈α
philosophers␈α
and␈α
scientists␈α∞would␈α
be␈α
reluctant␈α
to␈α
introduce␈α∞such␈α
␈↓↓things,␈↓␈α
but␈α
the␈α∞fact␈α
that
␈↓ ↓H␈↓ordinary␈α
language␈α
allows␈α
␈↓↓"something␈α
wrong␈α
with␈α
the␈α
boat"␈↓␈α
suggests␈α
that␈α
we␈α
shouldn't␈α
be␈α
hasty␈αin
␈↓ ↓H␈↓excluding␈α∪it.␈α∀ Making␈α∪a␈α∪suitable␈α∀formalism␈α∪may␈α∪be␈α∀technically␈α∪difficult␈α∀and␈α∪philosophically
␈↓ ↓H␈↓problematical, but we must try.

␈↓ ↓H␈↓␈↓ α_In␈α
compensation,␈αwe␈α
may␈α
get␈αan␈α
increased␈αability␈α
to␈α
understand␈αnatural␈α
language,␈αbecause␈α
if
␈↓ ↓H␈↓natural␈αlanguage␈αadmits␈αsomething␈αlike␈αminimal␈αreasoning,␈αit␈αis␈αunderstandable␈αthat␈αwe␈αwill␈αhave
␈↓ ↓H␈↓difficulty in translating it into logical formalisms that don't.
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 95


␈↓ ↓H␈↓␈↓ α_The␈α⊗possibility␈α⊗of␈α⊗forming␈α⊗minimal␈α⊗completions␈α⊗of␈α⊗various␈α⊗parts␈α⊗of␈α⊗our␈α∃knowledge
␈↓ ↓H␈↓introduces␈α∂a␈α∂kind␈α∂of␈α∂fuzziness␈α∂that␈α∂I␈α∂believe␈α∂may␈α∂prove␈α∂more␈α∂fruitful␈α∂than␈α∂that␈α∂explicated␈α∂by
␈↓ ↓H␈↓fuzzy set theory.


␈↓ ↓H␈↓αMinimal models and minimal entailment in propositional calculus.

␈↓ ↓H␈↓␈↓ α_As␈α⊗the␈α⊗above␈α⊗indicates,␈α⊗developing␈α⊗techniques␈α⊗for␈α⊗minimal␈α⊗entailment␈α⊗and␈α⊗minimal
␈↓ ↓H␈↓inference␈αand␈αaxiomatizing␈αcommon␈αsense␈αknowledge␈αin␈αa␈αform␈αsuitable␈αfor␈αcomputer␈αuse␈αwill␈αbe
␈↓ ↓H␈↓difficult.␈α Therefore␈α
it␈αseems␈αworthwhile␈α
to␈αstudy␈αa␈α
propositional␈αcalculus␈αanalog␈α
of␈αthe␈αfirst␈α
order
␈↓ ↓H␈↓logic situation even though we haven't found any direct applications of the propositional case.

␈↓ ↓H␈↓␈↓ α_Suppose␈α
we␈α
have␈α
some␈α
facts␈α
to␈α
express␈α
but␈α
have␈α
not␈α
yet␈α
chosen␈α
a␈α∞propositional␈α
language.
␈↓ ↓H␈↓Our␈α⊂first␈α⊃step␈α⊂is␈α⊃to␈α⊂introduce␈α⊃propositional␈α⊂letters␈α⊃␈↓↓p␈↓β1␈↓↓,...,p␈↓βn␈↓␈α⊂and␈α⊃to␈α⊂specify␈α⊃each␈α⊂of␈α⊃them␈α⊂as
␈↓ ↓H␈↓expressing␈α⊃some␈α⊃elementary␈α⊂fact.␈α⊃ We␈α⊃call␈α⊃this␈α⊂establishing␈α⊃a␈α⊃␈↓↓propositional␈α⊃co-ordinate␈α⊂system␈↓.
␈↓ ↓H␈↓Then␈αwe␈αexpress␈αthe␈αset␈α␈↓↓A␈↓␈αof␈αknown␈αfacts␈αas␈αa␈αsentence␈α␈↓↓AX␈↓␈αin␈αthis␈αco-ordinate␈αsystem.␈α A␈αmodel
␈↓ ↓H␈↓of␈αthe␈αfacts␈αis␈αany␈αassignment␈αof␈αtruth␈αvalues␈αto␈αthe␈α␈↓↓p␈↓βi␈↓'s␈αthat␈αmakes␈α␈↓↓AX␈↓␈αtrue.␈α Let␈α␈↓↓M1␈↓␈αand␈α␈↓↓M2␈↓␈αbe
␈↓ ↓H␈↓models of ␈↓↓AX.␈↓ We define

␈↓ ↓H␈↓␈↓ α_␈↓↓M1 ≤ M2 ≡  ∀i.(true(p␈↓βi␈↓↓,M2) ⊃ true(p␈↓βi␈↓↓,M1))␈↓.

␈↓ ↓H␈↓A␈α
minimal␈α
model␈α
is␈α
one␈α
that␈α
is␈α
not␈αa␈α
proper␈α
extension,␈α
i.e.␈α
a␈α
model␈α
in␈α
which␈α
(roughly␈αspeaking)␈α
as
␈↓ ↓H␈↓many␈αof␈α
the␈α␈↓↓p␈↓βi␈↓s␈αas␈α
possible␈αare␈αfalse␈α
-␈αconsistent␈α
with␈αthe␈αtruth␈α
of␈α␈↓↓AX␈↓.␈α ␈↓↓Note␈α
that␈αwhile␈αthe␈α
models
␈↓ ↓H␈↓↓of␈αa␈αset␈αof␈αfacts␈αare␈αindependent␈αof␈αthe␈αco-ordinate␈αsystem,␈αthe␈αminimal␈αmodels␈αdepend␈αon␈αthe␈αco-
␈↓ ↓H␈↓↓ordinate␈αsystem␈↓.␈α Here␈αis␈αthe␈αmost␈αtrivial␈αexample.␈α Let␈αthere␈αbe␈αone␈αletter␈α␈↓↓p␈↓␈αrepresenting␈αthe␈αone
␈↓ ↓H␈↓fact␈α∞in␈α
a␈α∞co-ordinate␈α
system␈α∞␈↓↓C,␈↓␈α
and␈α∞let␈α
␈↓↓A␈↓␈α∞be␈α
the␈α∞null␈α
set␈α∞of␈α
facts␈α∞so␈α
that␈α∞␈↓↓AX␈↓␈α
is␈α∞the␈α∞sentence␈α
␈↓↓T␈↓
␈↓ ↓H␈↓(identically␈α∂true).␈α⊂ The␈α∂one␈α∂other␈α⊂co-ordinate␈α∂system␈α⊂␈↓↓C'␈↓␈α∂uses␈α∂the␈α⊂elementary␈α∂sentence␈α⊂␈↓↓p'␈↓␈α∂taken
␈↓ ↓H␈↓equivalent␈α
to␈α
␈↓↓¬p␈↓.␈α The␈α
minimal␈α
model␈α
of␈α␈↓↓C␈↓␈α
is␈α
{¬p},␈αand␈α
the␈α
minimal␈α
model␈αof␈α
␈↓↓C'␈↓␈α
is␈α
{p}.␈α Since
␈↓ ↓H␈↓minimal␈α∞reasoning␈α
depends␈α∞on␈α
the␈α∞co-ordinate␈α
system␈α∞and␈α
not␈α∞merely␈α
on␈α∞the␈α
facts␈α∞expressed␈α
in
␈↓ ↓H␈↓the␈αaxioms,␈αthe␈αutility␈αof␈αan␈αaxiom␈αsystem␈αwill␈αdepend␈αon␈αwhether␈αits␈αminimal␈αmodels␈αexpress␈α
the
␈↓ ↓H␈↓uses we wish to make of Occam's razor.

␈↓ ↓H␈↓␈↓ α_A␈α∪less␈α∩trivial␈α∪example␈α∩of␈α∪minimal␈α∩entailment␈α∪is␈α∩the␈α∪following.␈α∩ The␈α∪propositional␈α∩co-
␈↓ ↓H␈↓ordinate␈α
system␈α∞has␈α
basic␈α
sentences␈α∞␈↓↓p␈↓β1␈↓,␈α
␈↓↓p␈↓β2␈↓␈α
and␈α∞␈↓↓p␈↓β3␈↓,␈α
and␈α
␈↓↓AX␈α∞=␈α
p␈↓β1␈↓↓␈α
∨␈α∞p␈↓β2␈↓.␈α
 There␈α
are␈α∞two␈α
minimal
␈↓ ↓H␈↓models.␈α
 ␈↓↓p␈↓β3␈↓␈α
is␈α
false␈αin␈α
both,␈α
and␈α
␈↓↓p␈↓β1␈↓␈αis␈α
false␈α
in␈α
one,␈αand␈α
␈↓↓p␈↓β2␈↓␈α
is␈α
false␈αin␈α
the␈α
other.␈α
 Thus␈α
we␈αhave
␈↓ ↓H␈↓␈↓↓AX ␈↓πq␈↓βm␈↓↓ (¬(p␈↓β1␈↓↓ ∧ p␈↓β2␈↓↓) ∧ ¬p␈↓β3␈↓).

␈↓ ↓H␈↓␈↓ α_Note␈α
that␈αif␈α
␈↓↓AX␈↓␈αis␈α
a␈α
conjunction␈αof␈α
certain␈αelementary␈α
sentences␈α
(some␈αof␈α
them␈αnegated),␈α
e.g.
␈↓ ↓H␈↓␈↓↓AX = p␈↓β2␈↓↓ ∧ ¬p␈↓β4␈↓,␈α∂then␈α∂there␈α∂is␈α∂a␈α∂unique␈α∂minimal␈α∂model,␈α∂but␈α∂if,␈α∂as␈α∂above,␈α∂␈↓↓AX = p␈↓β2␈↓↓ ∨ ¬p␈↓β4␈↓,␈α∂then
␈↓ ↓H␈↓there is more than one minimal model.

␈↓ ↓H␈↓␈↓ α_One may also consider extensions ␈↓↓relative␈↓ to a set ␈↓↓B␈↓ of elementary sentences.  We have

␈↓ ↓H␈↓␈↓ α_␈↓↓M1 ≤ M2 (mod B) ≡ ∀p.(p ε B ∧ true(p,M1) ⊃ true(p,M2)␈↓.

␈↓ ↓H␈↓We␈α⊂can␈α⊂then␈α⊂introduce␈α⊂minimal␈α⊂models␈α⊂relative␈α⊂to␈α⊂␈↓↓B␈↓␈α⊂and␈α⊂the␈α⊂corresponding␈α⊂relative␈α∂minimal
␈↓ ↓H␈↓entailment.␈α
 Thus␈α
we␈α
may␈α
care␈α
about␈α
minimality␈α∞and␈α
Occam's␈α
razor␈α
only␈α
over␈α
a␈α
certain␈α∞part␈α
of
␈↓ ↓H␈↓our knowledge.
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 96


␈↓ ↓H␈↓␈↓ α_Note␈α⊂that␈α⊂we␈α⊂may␈α⊂discover␈α⊂a␈α⊂set␈α⊂of␈α⊂facts␈α⊂one␈α⊂at␈α⊂a␈α⊂time␈α⊂so␈α⊂that␈α⊂we␈α⊂have␈α⊂an␈α⊂increasing
␈↓ ↓H␈↓sequence␈α⊂␈↓↓A␈↓β1␈↓↓␈α⊂⊂␈α⊂A␈↓β2␈↓␈α⊂⊂␈α⊂...␈α⊂of␈α⊂sets␈α⊂of␈α⊂sentences.␈α⊂ A␈α⊂given␈α⊂sentence␈α⊂␈↓↓p␈↓␈α⊂may␈α⊂oscillate␈α⊂in␈α⊃its␈α⊂minimal
␈↓ ↓H␈↓entailment␈α∞by␈α∂the␈α∞␈↓↓A␈↓βi␈↓,␈α∞e.g.␈α∂we␈α∞may␈α∂have␈α∞␈↓↓A␈↓β1␈↓π q␈↓βm␈↓↓ p␈↓,␈α∞␈↓↓A␈↓β2␈↓π q␈↓βm␈↓↓ ¬p␈↓,␈α∂neither␈α∞may␈α∞be␈α∂entailed␈α∞by␈α∂␈↓↓A␈↓β3␈↓,␈α∞etc.
␈↓ ↓H␈↓The␈α
common␈α∞sense␈α
Occam's␈α∞razor␈α
conclusion␈α
about␈α∞a␈α
sentence␈α∞␈↓↓p␈↓␈α
often␈α
behaves␈α∞this␈α
way␈α∞as␈α
our
␈↓ ↓H␈↓knowledge increases.
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 97


␈↓ ↓H␈↓αNotes

␈↓ ↓H␈↓␈↓ α_1.␈α
There␈α
is␈α∞a␈α
relation␈α
between␈α∞minimal␈α
entailment␈α
and␈α∞the␈α
THNOT␈α
formalism␈α∞of␈α
micro-
␈↓ ↓H␈↓planner.␈α (THNOT␈α␈↓↓p)␈↓␈αmeans␈αthat␈αan␈αattempt␈αto␈αprove␈α␈↓↓p␈↓␈αhas␈αfailed,␈αand␈αsuch␈αa␈αfailure␈α
to␈αprove
␈↓ ↓H␈↓something␈αwrong␈α
with␈αthe␈αboat␈α
could␈αlead␈αto␈α
a␈αplan␈αto␈α
row␈αacross␈αthe␈α
river.␈α Likewise␈α
failure␈αto
␈↓ ↓H␈↓prove the existence of a bridge can be used to go from the facts to the Amarel representation.

␈↓ ↓H␈↓␈↓ α_2.␈αWhen␈α
we␈αadd␈α
common␈αsense␈αknowledge␈α
or␈αgeneral␈α
scientific␈αknowledge␈α
to␈αthe␈αfacts␈α
about
␈↓ ↓H␈↓a␈α∩particular␈α∩problem,␈α∩we␈α∩get␈α⊃a␈α∩huge␈α∩collection␈α∩of␈α∩facts␈α⊃with␈α∩huge␈α∩models␈α∩most␈α∩of␈α∩which␈α⊃is
␈↓ ↓H␈↓irrelevant␈αto␈αthe␈αproblem.␈α
 The␈αusual␈αapproach␈αis␈α
for␈αthe␈αhuman␈αto␈α
separate␈αwhat␈αis␈αrelevant␈α
and
␈↓ ↓H␈↓make␈αan␈αaxiom␈αsystem␈αcontaining␈αonly␈α
relevant␈αinformation.␈α If␈αwe␈αwant␈αa␈αcomputer␈α
program␈αto
␈↓ ↓H␈↓express␈α∞what␈α∂it␈α∞knows␈α∞in␈α∂a␈α∞certain␈α∞language,␈α∂we␈α∞need␈α∞a␈α∂better␈α∞way.␈α∞ One␈α∂way␈α∞of␈α∂reducing␈α∞the
␈↓ ↓H␈↓number␈αof␈α
models␈αis␈αto␈α
say␈αthat␈α
two␈αmodels␈αare␈α
equivalent␈αif␈α
they␈αare␈αthe␈α
same␈αfor␈α
certain␈αsorts
␈↓ ↓H␈↓and␈αcertain␈αpredicates␈αand␈αfunctions.␈α We␈αthen␈α
work␈αwith␈αthe␈αequivalence␈αclasses␈αand␈αtry␈αto␈α
make
␈↓ ↓H␈↓a␈α∞set␈α∞of␈α
sentences␈α∞involving␈α∞only␈α
the␈α∞objects␈α∞in␈α∞these␈α
sorts␈α∞and␈α∞as␈α
few␈α∞others␈α∞as␈α∞possible␈α
whose
␈↓ ↓H␈↓models correspond to these equivalence classes.

␈↓ ↓H␈↓␈↓ α_3.␈αIn␈αthe␈αfirst␈αorder␈α
logic␈αtheory␈αwe␈αalso␈αneed␈α
to␈αconsider␈αextensions␈αand␈αminimality␈α
relative
␈↓ ↓H␈↓to a subcollection of the sorts.

␈↓ ↓H␈↓␈↓ α_4.␈α∂In␈α∂the␈α∂propositional␈α∂calculus␈α∂system␈α∂we␈α∂minimize␈α∂the␈α∂set␈α∂of␈α⊂propositional␈α∂co-ordinates
␈↓ ↓H␈↓assigned␈α∂␈↓αtrue␈↓␈α∂while␈α∞in␈α∂the␈α∂predicate␈α∂calculus␈α∞system␈α∂we␈α∂minimize␈α∂the␈α∞set␈α∂of␈α∂objects␈α∂asserted␈α∞to
␈↓ ↓H␈↓exist.␈α
 It␈α
might␈α
be␈α
worth␈α
considering␈α
co-ordinate␈α
systems␈α
in␈α
the␈α
predicate␈α
calculus␈α
system␈α
within
␈↓ ↓H␈↓which it is worthwhile to minimize the set of propositions asserted.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓␈↓εThis draft of MINIMA[F76,JMC] PUBbed at 19:20 on May 28, 1977.